This invention relates generally to computer systems, and more particularly to the rendering of characters to be displayed on computer output devices.
Computer systems typically include some form of visual output device. For example, in FIG. 1, a prior art computer system 10 includes a computer 12, a keyboard 14, a disk storage unit 16, a video display 18, and a printer 20.
Computer 12 includes a central processing unit (CPU) 22, read only memory (ROM) 24, random access memory (RAM) 26, and input/output (I/O) 28. The various components 22-28 of the computer 12 are coupled by a bus system 30. As will be appreciated by those skilled in the art, the representation of the computer 12 has been highly simplified for the purposes of this discussion, but includes the fundamental components of a computer and their interconnections.
Devices such as keyboard 14, disk storage 16, video display 18, and printer 20 are often referred to as xe2x80x9cperipheralxe2x80x9d devices. When coupled to the computer 12 they become part of computer system 10. Some peripheral devices are primarily for inputting information to the computer 12, other peripheral devices are used for outputting information from the computer 12, and some computer peripherals are used for both inputting and outputting information.
Video display 18 and printer 20 are common output devices for the computer 12. Such output devices typically form temporary or permanent images to convey information to a user of computer system 10. For example, video display 18 includes a screen that can display character, graphical, and other types of images.
A number of problems arise when displaying characters on a computer output device. The term xe2x80x9ccharacterxe2x80x9d, as used herein, is not limited to alphanumeric characters, but includes any form of character, number, symbol, or other coded device that can be represented or displayed on a computer output device. Some problems relate to the resolution of the output device, and other problems relate to human visual perception. xe2x80x9cResolutionxe2x80x9d, as it is used herein, refers to the size of individual pixels of a computer output device, and the spacing between the pixels of the output device.
The problems inherent in character imaging tend to be more pronounced for small characters than for larger characters. This is because small characters are made up of fewer pixels and, therefore, even a distortion of a few pixels is readily apparent in the smaller characters. Some of the distortions that may occur, particularly in these smaller characters, are: unbalanced xe2x80x9cstemxe2x80x9d widths, thin feature disconnection, over/under filling, and inaccurate weighting. One of the most noticeable of these defects is unbalanced stem widths, where vertical and horizontal strokes of characters may be of varying widths due to the character rendering process. Another very noticeable defect is the inaccurate weighting effect of small characters due to a quantization effect. Adding a pixel (the xe2x80x9cquantumxe2x80x9d) to a character stem that is only a few pixels wide can distort the xe2x80x9cweightxe2x80x9d given to that character, e.g. it may appear to be xe2x80x9cboldxe2x80x9d even when it is a normal weight character.
In FIG. 2A, the prior art problem of unbalanced stem widths is illustrated. In this instance, a lower case letter xe2x80x9cmxe2x80x9d is shown superimposed over a high-resolution grid 32 both in an outline form 34, and a xe2x80x9cbitmapxe2x80x9d form 36. xe2x80x9cBitmapxe2x80x9d refers to a one-to-one mapping between data stored in the memory of the computer 12 and an image of the character to be displayed, i.e. each pixel of the output device corresponds to a bit of information stored in the computer. The outline 34 is typically provided by a parsed font program such as described in Adobe Type I format, Version 1.1, available from Adobe Systems, Inc. of San Jose, Calif., often referred to as the xe2x80x9cBlack Bookxe2x80x9d due to the color of its cover. Character outline 34 is converted or xe2x80x9crenderedxe2x80x9d into the bitmap 36 by a rendering program or xe2x80x9crendererxe2x80x9d available from a variety of sources, including Adobe Systems, Inc.
In FIG. 2A, the letter xe2x80x9cmxe2x80x9d includes some distortion that is attributable to the conversion from font outline 34 to bitmap 36 form. In particular, the three vertical legs or xe2x80x9cstemsxe2x80x9d of the letter xe2x80x9cmxe2x80x9d are of different widths. As noted, the left stem 38a is two pixels wide, the middle stem 38b is one pixel wide, and the right stem 38c is two pixels wide.
While characters are often rendered on a high-resolution grid as illustrated in FIG. 2A, they must be converted into a xe2x80x9ccoarse gridxe2x80x9d representation before they can be displayed on the output device. The resolution of the coarse grid corresponds to the resolution of the output device.
In FIG. 2B, the conversion from a high-resolution grid to a coarse grid permits the renderer to re-balance the stems. More particularly, the system uses xe2x80x9chintsxe2x80x9d provided by the parsed font program to stretch and then align the stems of the character to the coarse grid. As noted, in FIG. 2B, the stems 40a, 40b, and 40c are all the same width and, therefore, the unbalanced stem problem can be resolved for black-and-white types of output devices.
While the prior art has solved the problem of unbalanced stem widths for black and white output devices, the problem has re-emerged for greyscale and color output devices. Some output devices use a technique known as xe2x80x9canti-aliasingxe2x80x9d in order to provide the illusion of smoother curves and less jagged diagonal lines. This is accomplished by varying greyscale or color values of the coarse grid. However, this manipulation can re-introduce the problem of unbalanced stem widths to anti-aliased characters.
In FIG. 2C, the lower case letter xe2x80x9cmxe2x80x9d is shown against a coarse grid 42 and corresponding high-resolution grid 44. The high-resolution grid 44 is shown in only one of the cells of the coarse grid 42 so as not to confuse the drawings, although it will be appreciated that the high-resolution grid 44 is associated with all the cells of the coarse grid 42. The coarse grid and the high-resolution grid are related as follows. If the output device has 2n+1 greyscale values, each xe2x80x9ccellxe2x80x9d 46 of the coarse grid 42 will have 2n pixels 48. To provide a more concrete example, if 17 greyscale levels are provided from pure white to pure black, then 24 or 16 pixels of the high-resolution grid are in each cell of the coarse grid 42. This means that the resolution of the high-resolution grid 44 is four times the resolution of the coarse grid 42. As before, the font outline 50 for the letter xe2x80x9cmxe2x80x9d is obtained, and a bitmap 52 is developed at the resolution of the high-resolution grid from the font outline 50 by the renderer.
In FIG. 2D, the bitmap 52 has been converted into a greyscale xe2x80x9cpixel mapxe2x80x9d which can be sent to the output device. The conversion is usually accomplished in a straightforward fashion. The number of pixels for a particular cell are counted, and this number is mapped to the greyscale level for that cell. Therefore, cells having more pixels will correspond to a darker greyscale value than cells having fewer pixels. This technique, referred to as xe2x80x9canti-aliasingxe2x80x9d, greatly smooths the appearance of curves and reduces the jaggedness of diagonal lines, as is well known to those skilled in the art.
As used herein, a xe2x80x9cpixel mapxe2x80x9d is much like a xe2x80x9cbitmapxe2x80x9d except that multiple values are stored in the memory of the computer system 12 which correspond to each pixel of the output device. For example, for each pixel on a greyscale or color video monitor, multiple sub-pixels can be defined each including a numeric value that is stored on the computer.
However, as seen in FIG. 2D, the unbalanced stem problem has reoccurred as a result of the application of the xe2x80x9canti-aliasingxe2x80x9d process. More particularly, stem 54a appears to be two pixels wide, while stems 54b and 54c appear to be about one pixel wide. Again, this stem unbalance phenomenon is quite apparent in small characters and reduces the quality of the output image.
While this discussion has centered on vertical stems, that the problem is equally apparent with horizontal stems. For example, while the example of the lower case xe2x80x9cmxe2x80x9d was given, this stem unbalancing problem is also apparent on letters such as an upper case xe2x80x9cE.xe2x80x9d Furthermore, both vertical and horizontal xe2x80x9cstemsxe2x80x9d or segments can be found in a single letter, such as the letter xe2x80x9coxe2x80x9d, which has two vertical side segments or stems, and two horizontal top and bottom segments or stems.
Some attempt has been made by output device manufacturers to enhance the image provided to the output device as a bitmap or a pixel map. For example, certain Hewlett-Packard Company printers provide xe2x80x9cimage enhancementxe2x80x9d which attempts to smooth xe2x80x9cjaggedxe2x80x9d diagonal lines and to smooth curves. While generally useful, such post-rendering image enhancement mechanisms are not completely successful because the information that was used to create the bitmap or pixel map (e.g. the font outline) is not available to the output device after the render process has been applied. Therefore, post-rendering image enhancement cannot correct problems such as unbalanced stem widths, etc.
Another technique for enhancing the image provided to the output device includes aligning stems on pixel boundaries and is described in co-pending U.S. patent application Ser. No. 08/547,562, filed Oct. 23, 1995, entitled xe2x80x9cMethod and Apparatus for Rendering Characters,xe2x80x9d to Terence Dowling, assigned to Adobe Systems, Inc of San Jose, Calif., the contents of which are expressly incorporated herein by reference. This technique does not suffer from the limitations provided by post-render solutions. However, the technique described in the Dowling application was limited in that the stem alignment was fixed to a single device grid and therefore to the device grid boundaries (pixel boundaries) defined therein.
Certain output devices, such as LCDs support sub-pixel addressing. Subpixel, as used herein, refers to a pixel component that is independently addressable in the output device. For example, in a conventional RGB color output LCD device, a single pixel includes three components, or sub-pixels, a red component, a green component and a blue component. Each of the three sub-pixels are independently addressable for each pixel, that is, each individual component can have a value set, the combination of which produce the color perceived by the user for a particular pixel location. In a conventional RGB LCD output device, the sub-pixels include a geometry, the sub-pixel geometry, that defines an physical arrangement of the sub-pixels on the output device. In one conventional RGB LCD output device, each sub-pixel is of the form of a color bar, and the bars are arranged as a horizontal row. Depending on the manufacturer of the output device, the ordering of the color bars may vary from device to device. For example, in a Colorbook device produced by Gateway Computers or a Inspiron 7000 device produced by Dell Computers, the sub-pixel geometry includes an arrangement of color bars in a horizontal row. Other geometries are possible including a closely packed hexagonal arrangement.
The present invention provides a method for precisely placing stems of a character and increasing the effective horizontal resolution of a output device by a factor in at least one dimension. In a conventional RGB LCD device, the effective resolution can be increased by an order of magnitude of three without increasing the cost/complexity of the output device.
In one aspect, the invention provides a computer-implemented method for processing a character for display on a raster output device where the output device has a resolution and a set of pixels defining a device grid. The method includes evaluating a plurality of alignment grids and selecting a best alignment grid for a stem of the character where the plurality of alignment grids from a set of grids. Each alignment grid in the set being is similar to the device grid but shifted by a phase difference equal to a sub-pixel dimension. The process includes rendering the character at a resolution higher than the resolution of the output device including aligning the stem using the selected alignment grid to a sub-pixel boundary and down sampling the rendered character to the resolution of the output device.
Aspects of the invention may include one or more of the following features. The character is created at a type size by a font having font metrics including hinting information defining a center of a stem. The step of evaluating includes laying down the character and determining an alignment grid that best aligns the center of the stem to a sub-pixel boundary. The method can further include receiving sub-pixel geometry information for the output device defining a geometry of the addressable sub-pixels for each pixel of the output device. The step of aligning the character can include using the sub-pixel geometry information to determine which sub-pixels of which pixels to illuminate when the character is not aligned to a pixel boundary. The step of down sampling can include receiving device specific data derived specifically for the output device where the device specific data includes a plurality of functions, one for each color plane used by the output device. The method can include determining an intensity for each sub-pixel of a pixel in the selected alignment grid using the device specific data to derive intensity data specifically for the output device. The sub-pixel dimension can be a sub-pixel width, height or height and width.
In another aspect, the invention provides a computer-implemented method for processing a character for display on a raster output device having an resolution defined by a set of output pixel positions: The method includes aligning a stem of the character to a best sub-pixel boundary, rendering the character at a resolution higher than the resolution of the raster output device and down sampling the aligned character to the raster output device resolution.
Aspects of the invention can include one or more of the following advantages. An advantage of the present invention is that the technique can be used to smooth curves and prevent jagged diagonal lines without introducing certain distortions into the image of the character being displayed while providing up to a threefold increase in the resolution in one dimension for an RGB output device. The invention accomplishes this task by aligning the high-resolution bitmap of the character to a sub-pixel boundary of an alignment grid and then mapping the alignment grid to the coarse grid during the rendering process.
These and other advantages of the present invention will become apparent upon reading the following detailed descriptions and studying the various figures of the drawings.